
#include <iostream>
#include <string>
#include <vector>
using std::endl;
using std::cout;
using std::string;
using std::vector;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList);

private:
    int CompareWord(const string& s1, const string& s2);
    bool isInArr(const string& word, const vector<string>& wordList);
};

int Solution::CompareWord(const string& s1, const string& s2) {
    auto it = s1.begin();
    auto it2 = s2.begin();
    int size = 0;

    while (it != s1.end() && it2 != s2.end()) {
        if (*it == *it2) {
            ++size;
        }

        ++it;
        ++it2;
    }

    return size;
}

bool Solution::isInArr(const string& word, const vector<string>& wordList) {
    for (const string& w : wordList) {
        if (w == word) {
            return true;
        }
    }

    return false;
}

int Solution::ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    int idx = 0;

    if (!isInArr(endWord, wordList)) {
        cout << "不存在" << endl;
        return 0;
    }

    while (beginWord != endWord) {
        bool found = false;
        //在外面找一次
        for (int i = 0; i < wordList.size(); i++) {
            cout<<beginWord<<endl;
            if (CompareWord(beginWord, wordList[i]) >= beginWord.size() - 1) {
                beginWord = wordList[i];
                wordList.erase(wordList.begin() + i);
                ++idx;
                found = true;
                break;
            }
        }

        if (!found) {
            cout << "无法找到路径" << endl;
            return 0;
        }
    }

    return idx;
}

int main() {
    Solution solution;
    
    string beginWord = "hit";
    string endWord = "cog";
    vector<string> wordList = {"hit","hot", "dot", "dog", "lot", "log", "cog"};
    
    int result = solution.ladderLength(beginWord, endWord, wordList);
    cout << "最短路径长度: " << result << endl;
    
    return 0;
}
